//524 通过删除字母匹配到字典里最长单词
/*
给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。

输入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
输出: 
"apple"

输入:
s = "abpcplea", d = ["a","b","c"]
输出: 
"a"



*/

//
class Solution
{
public:
    string findLongestWord(string s, vector<string> &dictionary)
    {
        string res = "";
        for (int i = 0; i < dictionary.size(); i++)
        {
            // 首先判断一波是否可以进行判断，如果是长度不够或者长度相等字典序大的直接剪枝
            if (res.length() > dictionary[i].length() || (res.length() == dictionary[i].length() && res.compare(dictionary[i]) < 0))
            {
                continue;
            }
            // 判断
            if (judge(s, dictionary[i]))
            {
                res = dictionary[i];
            }
        }
        return res;
    }

    bool judge(string s, string target)
    {
        int index1 = 0, index2 = 0;
        // 双指针判断target是否是s的子序列
        while (index1 < s.length() && index2 < target.length())
        {
            if (s[index1] == target[index2])
            {
                index2++;
            }
            index1++;
        }
        return index2 == target.length();
    }
};
